package com.c2b.algorithm.leetcode.lcr;

/**
 * <a href='https://leetcode.cn/problems/intersection-of-two-linked-lists/description/'>相交链表(Intersection of Two Linked Lists)</a>
 * <p>给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。</p>
 * <p>题目数据 保证 整个链式结构中不存在环。</p>
 * <p>注意，函数返回结果后，链表必须 保持其原始结构 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *     <a href='https://leetcode.cn/problems/intersection-of-two-linked-lists/description/'>查看示例</a>
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>listA 中节点数目为 m</li>
 *         <li>listB 中节点数目为 n</li>
 *         <li>1 <= m, n <= 3 * 10^4</li>
 *         <li>1 <= Node.val <= 10^5</li>
 *         <li>0 <= skipA <= m</li>
 *         <li>0 <= skipB <= n</li>
 *         <li>如果 listA 和 listB 没有交点，intersectVal 为 0</li>
 *         <li>如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]</li>
 *     </ul>
 * </p>
 * <b>进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？</b>
 *
 * @author c2b
 * @since 2024/3/19 17:21
 */
public class LCR023 {
    public static class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) {
                return null;
            }
            int diff = 0;
            ListNode tempNode = headA;
            while (tempNode != null) {
                tempNode = tempNode.next;
                ++diff;
            }
            tempNode = headB;
            while (tempNode != null) {
                tempNode = tempNode.next;
                --diff;
            }
            if (diff > 0) {
                for (int i = 0; i < diff; i++) {
                    headA = headA.next;
                }
            } else {
                for (int i = 0; i < -diff; i++) {
                    headB = headB.next;
                }
            }
            while (headA != null && headA != headB) {
                headA = headA.next;
                headB = headB.next;
            }
            return headA;
        }
    }
}
